package com.naokeziteng.dijkstra.domain;

import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * @author hawk
 * @date 2022/10/15
 * @desc 图
 **/
public class Graph {

    //顶点数量
    private int V;
    //边数量
    private int E;
    //邻接矩阵<顶点id,权重>
    private TreeMap<String, TreeMap<String, Double>> adj;
    //顶点列表
    private final List<Vertex> vertices;

    //建图 O(E)
    public Graph(List<Vertex> vertices, List<Edge> edges) {
        this.V = vertices.size();
        this.E = edges.size();
        this.vertices = vertices;
        adj = new TreeMap<>();

        for (Edge edge : edges) {
            String start = edge.getStart();
            String end = edge.getEnd();
            double weight = edge.getWeight();
            adj.computeIfAbsent(start, k -> new TreeMap<>());
            adj.computeIfAbsent(end, k -> new TreeMap<>());
            //自环边
            if (start.equals(end)) {
                throw new IllegalArgumentException("self loop is detected!");
            }
            //平行边
            if (adj.get(start).containsKey(end)) {
                throw new IllegalArgumentException("parallel edges are detected!");
            }
            adj.get(start).put(end, weight);
            adj.get(end).put(start, weight);
        }
    }

    public int V() {
        return V;
    }

    public int E() {
        return V;
    }

    //是否存在边 O(1)
    public boolean hasEdge(String v, String w) {
        return adj.get(v).containsKey(w);
    }

    //获取相邻的边 O(V)
    public Iterable<String> adj(String v) {
        return adj.get(v).keySet();
    }

    //获取边的权重
    public double getWeight(String v, String w) {
        if (hasEdge(v, w)) {
            return adj.get(v).get(w);
        }
        throw new IllegalArgumentException(String.format("No edge %s-%s", v, w));
    }

    //求一个顶点的度(相邻边的个数) O(V)
    public int degree(String v) {
        return adj.get(v).size();
    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("V = %d, E = %d\n", V, E));
        for (Vertex v : vertices) {
            String vertexId = v.getVertexId();
            sb.append(String.format("%s: ", vertexId));
            if (adj.get(vertexId).isEmpty()) {
                sb.append("()");
                continue;
            }
            for (String w : adj.get(vertexId).keySet()) {
                sb.append(String.format("(%s , ", w)).append(String.format("%f)", adj.get(vertexId).get(w)));
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    @Override
    protected Object clone() {
        try {
            Graph cloned = (Graph) super.clone();
            cloned.adj = new TreeMap<>();
            for (Vertex v : vertices) {
                String vertexId = v.getVertexId();
                cloned.adj.put(vertexId, new TreeMap<>());
                for (Map.Entry<String, Double> entry : adj.get(vertexId).entrySet()) {
                    cloned.adj.get(vertexId).put(entry.getKey(), entry.getValue());
                }
            }
            return cloned;
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return null;
    }

}
